/*
 * @lc app=leetcode.cn id=17 lang=cpp
 *
 * [17] 电话号码的字母组合
 *
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 *
 * algorithms
 * Medium (58.96%)
 * Likes:    2749
 * Dislikes: 0
 * Total Accepted:    808.6K
 * Total Submissions: 1.4M
 * Testcase Example:  '"23"'
 *
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * 
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：digits = ""
 * 输出：[]
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：digits = "2"
 * 输出：["a","b","c"]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 0 <= digits.length <= 4
 * digits[i] 是范围 ['2', '9'] 的一个数字。
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    void BackTracking(const string& digits, const vector<string>& letters, 
        vector<string>& result, string& path,
        int digitsIndex) {
        if (path.size() == digits.size()) {
            result.push_back(path);
            return;
        }

        const string& letter = letters[digits[digitsIndex] - '0'];
        for (int i = 0; i < letter.size(); i++) {
            path.push_back(letter[i]);
            BackTracking(digits, letters, result, path, digitsIndex + 1);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0)
            return {};

        vector<string> letters = {
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };

        vector<string> result;
        string path;

        //digitsIndex 这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串）
        //同时index也表示树的深度。
        BackTracking(digits, letters, result, path, 0);

        return result;
    }
};
// @lc code=end

